package com.algrithom.stack;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

import org.apache.commons.lang3.StringUtils;

/**
 * 全排列
 *
 * @author think
 * @version 1.0.0
 * @since 2019/12/21
 */
public class FullPermutation {
    
    private final List<List<Integer>> res = new LinkedList<>();
    
    /**
     * 全排列
     *
     * @param args 参数
     */
    public static void main(String[] args){
        int n = 5;
        int[] array = new int[n];
        // permutaion(n, array, 0);
        //        permutation1("", 3);
        int[] matrix = {1,2,3};
        FullPermutation fullPermutation = new FullPermutation();
        List<List<Integer>> result = fullPermutation.permute(matrix);
        for (List<Integer> list : result) {
            System.out.println(StringUtils.join(list));
        }
    }
    
    private static void permutaion(int n,int[] array,int cur){
        if (cur == n) {
            System.out.println(Arrays.toString(array));
        }
        for (int i = 1; i <= n; i++) {
            boolean ok = true;
            // 判断数组中是否已经包含了这个元素
            for (int j = 0; j < cur; j++) {
                if (array[j] == i) {
                    ok = false;
                }
            }
            // 不包含这个元素就放进去
            if (ok) {
                array[cur] = i;
                permutaion(n,array,cur + 1);
            }
        }
    }
    
    private static void permutation1(String str,int n){
        if (str.length() == n) {
            System.out.println(str);
        } else {
            for (int i = 1; i <= n; i++) {
                if (!str.contains(String.valueOf(i))) {
                    permutation1(str + i,n);
                }
            }
        }
    }
    
    /* 主函数，输入一组不重复的数字，返回它们的全排列 */
    private List<List<Integer>> permute(int[] nums){
        // 记录「路径」
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(nums,track);
        return res;
    }
    
    void backtrack(int[] nums,LinkedList<Integer> track){
        // 触发结束条件
        if (track.size() == nums.length) {
            res.add(new LinkedList<>(track));
            return;
        }
        
        for (int num : nums) {
            // 排除不合法的选择
            if (track.contains(num)) {
                continue;
            }
            // 做选择
            track.add(num);
            // 进入下一层决策树
            backtrack(nums,track);
            // 取消选择
            track.removeLast();
        }
    }
}
